#function LevenshteinDistance(char s[1..m], char t[1..n]):
#    set each element in d to zero
#
#    for i from 1 to m:
#        d[i, 0] := i
#
#    for j from 1 to n:
#        d[0, j] := j
#
#    for j from 1 to n:
#        for i from 1 to m:
#            if s[i] = t[j]:
#                substitutionCost := 0
#            else:
#                substitutionCost := 1
#
#            d[i, j] := minimum(d[i-1, j] + 1,
#                            d[i, j-1] + 1,
#                            d[i-1, j-1] + substitutionCost)
#    return d[m, n]


# 矩阵存储距离

def LevenshteinDistance(s,t):
    d = [[0]*(len(t)+1)]*(len(s)+1)
    print(d)
    for i in range(len(s)+1):
        k = i
        print(d)
        d[k][0] = i
    print(d)
    for j in range(len(t)+1):
        d[0][j] = j
    print(d)
    for j in range(1,len(t)+1):
        for i in range(1,len(s)+1):
            if s[i-1] == t[j-1]:
                substitutionCost = 0
            else:
                substitutionCost = 1

            d[i][j] = min([d[i - 1][j] +1 ,
                        d[i][j -1] +1 ,
                        d[i-1][j-1] + substitutionCost])
    print(d) 
    return d[len(s)][len(t)]

result = LevenshteinDistance("hello","hell")
print(result)
